#include<bits/stdc++.h>
using namespace std;

int n,m,q;
int a[160010];

int rm[160010];

int main(){
	freopen("clear.in","r",stdin);
	freopen("clear.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		int lst=0;
		set<pair<int,int> > st;
		long long ans=0;
		for(int i=l;i<=r+1;++i){
			int cur=(i==r+1?0:a[i]);
			int dif=cur-lst;
			if(dif>0){
				rm[i]=dif;
				st.insert(make_pair(i%m,i));
			}
			if(dif<0){
				while(dif<0){
					auto it=st.lower_bound(make_pair(i%m,-1));
					if(it==st.end()){
						it=st.lower_bound(make_pair(-1,-1));
					}
					long long coef=(i-(*it).second+m-1)/m;
					long long del=min(-dif,rm[(*it).second]);
					ans+=coef*del;
					dif+=del;
					rm[(*it).second]-=del;
					if(rm[(*it).second]==0){
						st.erase(it);
					}
				}
			}
			lst=cur;
		}
		cout<<ans<<endl;
	}
	return 0;
}